package gold.digger;

import gold.utils.InputUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC57 {
    public long startExecuteTime = System.currentTimeMillis();

    //Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
//Output: [[1,2],[3,10],[12,16]]
//Explanation: Because the new interval [4,8]
    class Solution {
        public int[][] insert(int[][] intervals, int[] newInterval) {
            List<int[]> res = new ArrayList<>();
            boolean hasAddedExtra = false;
            for (int[] interval : intervals) {
                if (interval[1] < newInterval[0]) {
                    res.add(interval);
                    continue;
                }

                if (interval[0] > newInterval[1]) {
                    if (!hasAddedExtra) {
                        res.add(newInterval);
                        hasAddedExtra = true;
                    }
                    res.add(interval);
                    continue;
                }

                newInterval[0] = Math.min(interval[0], newInterval[0]);
                newInterval[1] = Math.max(interval[1], newInterval[1]);
            }

            if (!hasAddedExtra) res.add(newInterval);
            return (int[][]) res.toArray(new int[0][]);
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[][] intervals = InputUtil.toDoubleIntegerArray("[[2,5],[6,7],[8,9]]");
        int[] newInterval = InputUtil.toIntegerArray("[0,1]");
        System.out.println(solution.insert(intervals, newInterval));
    }

    public static void main(String[] args) throws Exception {
        LC57 an = new LC57();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
